A Viterbi decoder is a maximum likelihood decoder that provides forward error correction. Viterbi decoders are used to decode a sequence of encoded symbols, such as a bit stream. The bit stream can represent encoded information in a telecommunication system. Such encoded informnation can be transmitted through various media with each bit (or set of bits representing a symbol instant. In the decoding process, the Viterbi decoder works back through a sequence of possible bit sequences at each symbol instant to determine which one bit sequence is most likely to have been transmitted. The possible transitions from a bit at one symbol instant, or state, to a bit at a next, subsequent, symbol instant or state is limited. Each possible transition from one state to a next state can be shown graphically and is defined as a branch. A sequence of interconnected branches is defined as a path. Each state can transition only to a limited number of next states upon receipt of the next bit (or set of bits) in the bit stream. Thus, some paths survive and other paths do not survive during the decoding process. By eliminating those transitions that are not permissible, computational efficiency can be achieved in determining the most likely paths to survive. The Viterbi decoder typically defines and calculates a branch metric associated with each branch and employs this branch metric to determine which paths survive and which paths dot not survive.
A branch metric is calculated at each symbol instant for each possible branch. Each path has an associated metric, accumulated cost, that is updated at each symbol instant. For each possible transition, the accumulated cost for the next state is calculated as the lesser of the sum of the branch metric for the possible transitions and the path accumulated cost at the respective previous state.
Prior art decoders have used two arrays of registers in a predefined group of memory locations within random access memory to store the present state accumulated costs and next state accumulated cost. The registers of a first array were used to store the present state accumulated costs. As the accumulated costs were calculated for the next symbol instant, the present state accumulated costs were read from registers of the first array and used in the calculations. The calculated accumulated costs for the next symbol instant, or next state, were written to registers of a second array. After all of the accumulated costs for the next state were calculated, the next state accumulated costs were read from a register or location in the second array and written to a corresponding register or location in the first array. This transfer was made in preparation for decoding the next symbol in the bit stream through a subsequent series of calculations to update the accumulated costs at the next state. In this manner, current state accumulated costs were stored in registers of a first array. The next state accumulated costs were calculated and stored in registers of a second array. As a result, at each symbol instant, the operation of reading and writing the contents of the registers of the second array into corresponding registers of the first array was required. Depending on the number of branches, this required a large number of read/write operations. These data transfer operations decrease performance of the decoder both in terms of time lost in unproductive operations and in energy consumption, particularly, in battery powered devices such as mobile telephones.
Other prior art decoders using two arrays of registers have used a pointer to eliminate the data transfer operations. The pointer points to one of the two arrays. As the next state accumulated costs are calculated based on current state accumulated costs stored in registers of one of the arrays, the newly calculated next state accumulated costs are stored in registers of the other array to which the pointer points. When all of the accumulated costs are updated, the pointer is changed to point to the first array and the accumulated costs are updated. While this eliminates the data transfer operations, it still requires twice as many registers as accumulated costs.
A need remains in the art for an efficient way to calculate and store the accumulated costs that eliminates both the unnecessary read and write operations to transfer the accumulated costs from registers of one array to registers of another array and the necessity for twice as many registers as accumulated costs.